package org.datastructure.firstday.huffman;

import java.util.ArrayList;
import java.util.Collections;

public class HuffmanTreeDemo {

    public static void main(String[] args) {

        int[] arr = {6, 8, 12, 4, 20};
        Node huffman = createHuffman(arr);
        huffman.preOrder();

    }


    public static Node createHuffman(int[] arr) {
        ArrayList<Node> nodes = new ArrayList<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
            nodes.add(new Node(arr[i]));
        }

        // TODO: 2022/1/7 循环处理直到列表只剩一个元素，说明所有的节点和子树已处理完
        for (int i = arr.length; i  > 1; i--) {

            // TODO: 排序
            Collections.sort(nodes);
            // TODO: 2022/1/7 取出最小的两个子树（一个节点也可以看作一个子树）
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            // TODO: 将两个子树的权相加创建父节点，并将左子节点和右子节点添加到父节点
            Node parent = new Node(leftNode.getNo() + rightNode.getNo());
            parent.setLeft(leftNode);
            parent.setRight(rightNode);
            // TODO: 将父节点添加到新的排序队列，并将使用过的子树移除
            nodes.add(parent);
            nodes.remove(leftNode);
            nodes.remove(rightNode);
        }
        return nodes.get(0);
    }
}


